package com.demo.javaDemo.concurrent;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class ForkJoinQueen {
	
	private static class QueenCounter extends RecursiveTask<Long> {
		private static final long serialVersionUID = 1L;
		public final int len;
		public final int row;
		public final int lastRow;
		public int[] data;
		QueenCounter(int[] data,int row,int len){
			this.data=data;
			this.row=row;
			this.len=len;
			this.lastRow=len-1;
		}
		@Override
		protected Long compute() {
			if(row==len){
				//System.out.println(Arrays.toString(data));
				return 1l;
			}
			long size = 0;
            List<ForkJoinTask<Long>> tasks = new ArrayList<ForkJoinTask<Long>>(); 
            for(int i=0;i<len;i++){
				if(isOk(data,row,i)){
					//最后一位不再启动线程
					if(row==lastRow){
						size++;
					}else{
						int[] ndata=Arrays.copyOf(data, len);
						ndata[row]=i;
						tasks.add(new QueenCounter(ndata,row+1,len));
					}
				}
			}
			 for (final ForkJoinTask<Long> task : invokeAll(tasks)) { 
                 size += task.join(); 
             }
			//System.out.println(Arrays.toString(Arrays.copyOf(data, row))+":"+size);
			return size;
		} 
		public  boolean isOk(int[] data,int row,int num){
			for(int i=0;i<row;i++){
				int n=data[i];
				//同一列
				if(n==num){
					return false;
				}
				//斜线x-y=c
				if((n-i)==(num-row)){
					return false;
				}
				//反斜线x+y=c
				if((n+i)==(num+row)){
					return false;
				}
			}
			return true;
		}
		
	}
	public static void main(String[] args) {
		final long start = System.nanoTime(); 
		ForkJoinPool forkJoinPool = new ForkJoinPool();
		int len=10;
		long total = forkJoinPool.invoke(new QueenCounter(new int[len], 0,len));
		final long end = System.nanoTime(); 
        
        System.out.println("total:"+total+"\nTime taken: " + (end - start)/1000_000); 
		
	}
	public static String str(int[] rs){
		int len=rs.length;
		StringBuffer str=new StringBuffer();
		for(int num:rs){
			str.append("\n");
			for(int i=0;i<len;i++){
				str.append(i==num?"*":"\t");
			}
		}
		return str.substring(1);
	}
	
	
	

}
